package com.chenxys.algorithm.newbie;

/**
 * <p>
 *      二分法：
 *          局部最小值问题：数组无序，相邻位置不相等 <br/>
 *          局部最小：<br/>
 *              1): [0] < [1] --> [0]最小<br/>
 *              2): [N-2] > [N-1] --> [N-1]最小<br/>
 *              3): [左] > [i] < [右] -->[i]最小<br/>
 *
 *       解析：<br/>
 *          若满足条件1，则直接返回[0];若满足条件2，则直接返回[N-1]。若既不满足条件1，又不满足条件2，则意味着，[0]>[1] 且 [N-2]<[N-1],
 *          又因为其相邻位置不相等[可理解为先单调递减再单调递增]，则在下标0...N-1位置，一定存在一个数局部最小<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/25/23 11:33 PM
 * @Copyright ©
 */
public class DichotomyV4 {
    /**
     * <p>
     *     找到数组中的任意一个局部最小
     * </p>
     * @param arr 无序数组
     * @return 局部最小值下标
     */
    public static int oneMinIndex(int[] arr){
        if (arr == null || arr.length == 0) return -1;
        int N = arr.length;
        if (N == 1) return 0;
        if (arr[0] < arr[1]) return 0;
        if (arr[N - 1] < arr[N - 2]) return N-1;
        // arr.length > 2
        int L = 0;
        int R = N - 1;
        // 三个数以上，验证局部最小
        while (L < R - 1){
            int mid = (L + R) / 2;
            // [i] < [i-1] 且 [i] < [i + 1]
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                // 1 左 > 我 > 右
                // 2 左 < 我 > 右
                // 3 左 < 我 < 右
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }


    /**
     * <p>
     *     找到数组中 任意一个局部最小
     * </p>
     * @param arr 随机数组
     * @param minIndex 局部最小值位置
     * @return 是否局部最小
     */
    public static boolean check(int[] arr, int minIndex){
        if (arr.length == 0 ) return minIndex == -1;
        int left = minIndex - 1;
        int right = minIndex + 1;
        // 当前最小值的左边位置
        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        // 当前最小值的右边位置
        boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
        return leftBigger && rightBigger;
    }

    /**
     * <p>
     *     生成随机数组,相邻位置不相等
     * </p>
     * @param maxSize 数组最大长度
     * @param maxValue 数组最大值
     * @return 随机数组
     */
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new  int[(int) ((maxSize + 1) * Math.random())];
        if (arr.length > 0){
            arr[0] = (int) ((maxValue + 1) * Math.random() - (int) (maxValue * Math.random()));
            for (int i = 1; i < arr.length; i++) {
                do {
                    arr[i] = (int) ((maxValue + 1) * Math.random() - (int) (maxValue * Math.random()));
                } while (arr[i] == arr[i-1]);
            }
        }
        return arr;
    }


    /**
     * <p>
     *     打印数组
     * </p>
     * @param arr 数组
     */
    public static void printArray(int[] arr){
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("Test Start!");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int ans = oneMinIndex(arr);
            if (!check(arr, ans)) {
                printArray(arr);
                System.out.println("error!!!" + ans );
            }
        }
        System.out.println("Test End!");
    }
}
